Based on that Internet has been become explosively widespread, table scale for routers and switches in a network is significantly enlarged so that it should address to speed up table search. A ternary content addressable memory (TCAM) is paid attention as means of solving the problem in terms of the hardware.
FIG. 2 is a schematic view of a router configuration. The figure is an example of a router comprised of a network interface NIF, a network processor NP, a search engine SE, a lookup table LUT and a content memory CM. The network interface NIF and the network processor NP are connected though a system bus SBS. The network processor NP and the search engine SE are connected through an inner bus IBS. The search engine SE and the lookup table LUT are connected through a data bus DQ. Where the lookup table LUT is a TCAM, the content memory CM is a static random access memory (SRAM) or a dynamic random access memory (DRAM). The router transmits/receives packets from Internet network IPN through the network interface NIF. The network processor NP decodes and reconfigures the content of the packet received. For example, a destination Internet protocol address (IP address) read from the header of the packet is transferred to the lookup table LUT through the search engine SE. The lookup table LUT stores a plurality of destination IP addresses and generates an address to read from information regarding the destination IP address from the content memory CM if the inputted destination IP address is stored therein. The content memory CM stores such as path information and port numbers required to transfer packets and outputs information corresponding to the address which is inputted through a content memory address bus CADD to the network processor NP though the content bus CBS and the search engine SE. The network processor NP reconfigures the content of the header based on the information and transfers the packet from the designated port to the next relay point.
Non-patent document 1: IEEE, Journal of Solid-state circuits, vol. 31, No. 11, November 1996, p 1601-1609 describes a TCAM cell configuration in the TCAM. FIG. 3 shows a cell configuration of FIG. 1 of the non-patent document 1. The cell is comprised of the following three circuit blocks: a first block is a memory cell SMC31 comprised of NMOS transistor N311, N312, N313 and N314, and PMOS transistor P311 and 312 as well as so called SRAM cell; a second circuit block is a memory cell SMC 32 comprised of NMOS transistor N321, N322, N323 and N324, and PMOS transistor P321 and P322 as well as the memory cell SMC31; a third circuit block is a comparator MUC comprised of NMOS transistor N331, N332, N333, N334 and N335. The memory cell SMC31 stores binary information ‘0’ or ‘1’ and the memory cell SMC32 stores a third information ‘X’ so called “Don't care” state, respectively. These information can be written and read as known SRAMs by selectively activating a word line WL31 or WL32. The comparator MUC performs XNOR-operation to compare storage information and input information.
A search operation in the case where the storage information is ‘1’ is described for example. In this case, it is assumed that a storage node NT is driven to a source voltage VDD and a storage node NB is driven to a ground voltage VSS in the memory cell SMC311. Now if it is assumed that the TCAM cell is not “Don't care” state and a storage node DC in the memory cell SMC32 is driven to the source voltage VDD, the transistor N331 and N335 in the comparator MUC are conductive, respectively, and the transistor N332 is cut off. In this state, if a match line ML is precharged to the voltage higher than the ground voltage VSS and then the information ‘1’ is inputted, a bit line BLB among a bit line BLT and the bit line BLB with the ground voltage VSS is driven to the source voltage VDD so that the transistor N334 in the comparator MUC is conductive. However since the transistor N332 is cut off, the relation between the match line ML and the ground electrode is kept to be opened. Accordingly, the voltage of the match line ML kept at the precharge voltage is discriminated by a match line sense amplifier (not shown in the figure) so that it is determined that the compared information are matched. Alternatively, if the information ‘0’ is inputted, the bit line BLT among the bit line BLT and the BLB with the ground voltage VSS is driven to the source voltage VDD so that the transistor N333 in the comparator MUC is conductive. Accordingly, the match line ML and the ground electrode are short-circuited through the transistor N335, N331 and N333 so that the match line ML is discharged. That is to say, the match line sense amplifier discriminates that the voltage of the match line ML is decreased so that the compared information are not matched. If the TCAM cell in the figure is “Don't care” state, since the storage node DC in the memory cell SMC 32 is driven to the ground voltage VSS, the transistor N335 in the comparator MUC is cut off. Therefore, since even if any information is inputted, a current path between the match line ML and the ground electrode is not formed, the match line ML is kept at the precharge voltage so that it is forcibly determined that the compared information are matched. Additionally, in case of the third information ‘x’ that the input information indicates so-called “masking”, both of the bit line BLT and BLB are kept at the ground voltage VSS so that the transistor N333 and N334 in the comparator MUC are cut off. Therefore, even if the memory cell SMC31 stores any information, a current path is not also formed between the match line ML and the ground electrode so that the match line ML is kept the precharge voltage thereby it is forcibly determined that the compared information are matched.
Non-patent document 2: Records of the 2000 IEEE International Workshop on Memory Technology, Design and Testing, 2000, p 101-105 describes another TCAM cell configuration. FIG. 4 is the cell configuration of FIG. 2 of the non-patent document 2. The cell includes a storage node N1 and N2 comprised of NMOS transistor T1, T2, T4 and T6, and capacitor C1 and C2 and stores ternary information. The cell has XNOR calculation function by transistor T3, T4, T5, and T6 and compares the storage information and the input information.
Firstly, the memory function is described. The ternary information consists of information ‘1’, information ‘0’ and information ‘x’ indicating “Don't care” state. If high voltage is logic ‘1’ and low voltage is logic ‘0’, the logic value of the storage nodes (N1, N2) are in the case of the information ‘1’ is (1, 0), in the case of the information ‘0’ is (0, 1) and in the case of the information ‘X’ is (0, 0). The refresh of the storage information is performed through the transistor T1 and T2. A read and rewrite is performed using sense amplifiers connected to the bit line BL1 and BL2, respectively (not shown in the figure).
Next, the XNOR calculation function is described. The information to be compared with the storage information is inputted through the search line SL1 and SL2 and is ternary information. The ternary information consists of information ‘1’, information ‘0’ and information ‘X’ indicating masking. If both information are matched in the comparison operation, a current path is not formed between the match line precharged to the high voltage and a discharge line DCL fixed to the low voltage (for example ground voltage VSS) so that the match line is kept the precharge voltage. Alternatively, if the information are not matched, a current path is formed between the match line ML and the discharge line DCL so that the match line ML is discharged. The voltage variation of the match line ML by the above described operation is discriminated by the match line sense amplifiers (not shown in the figure) to determine the result of comparison. Incidentally, if the storage information and the input information are ‘X’, a current path is not formed between the match line ML and the discharge line DCL so that it is determined that the compared information are matched.
Patent document 1: U.S. patent application Ser. No. 6,288,922 describes further another TCAM cell configuration. FIG. 5 of the present application is the cell configuration shown in FIG. 4 of the patent document 1. The cell TMC is comprised of four memory cells HMC0-HMC3 arranged at the intersecting points of the match line ML and comparison data line C0-C3, respectively. Each memory cell is comprised of a NMOS transistor T51 and T52, and a memory circuit SC. A node to which the memory circuit SC and the gate electrode of the transistor T51 are connected is referred to as a storage node. Storage nodes D0-D3 are clearly shown in order to discriminate per memory cell in the figure. Since such cell TMC corresponds to double TCAM cells of FIG. 4, it is referred to as twin TCAM cell.
FIG. 19 is a data pattern of the twin TCAM for the ternary value. The data pattern of the comparison information is defined such that any one of comparison data lines C0-C3 is driven to the logical value ‘1’ for 00-11 (binary value), respectively. Meanwhile the memory circuit SC of each memory cell MC0-MC3 stores the value that the polarity of the logical value defined by the comparison data lines C0-C3 is inverted. The data pattern on storing the ternary value is the value obtained by the AND-operation regarding the storage information of the corresponding binary value per bit. For example, the data pattern corresponding to the ternary information ‘XO’ is a pattern ‘1010’ as the result of the AND operation per bit regarding the storage information ‘1110’ corresponding to the binary value ‘00’ and the storage information ‘1011’ corresponding to the binary value ‘10’. Such definition of the logical value causes the number of the comparison data line to be driven to decrease so that the power consumption for the search operation can be reduced.